#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;




//												替换所有的问号
class Solution
{
public:
    string modifyString(string s)
    {
        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '?')
            {
                for (char c = 'a'; c <= 'z'; c++)
                {
                    //if(c != s[i-1] && c!= s[i+1])
                    if ((i == 0 || c != s[i - 1]) && (i == n - 1 || c != s[i + 1]))
                    {
                        s[i] = c;
                        break;
                    }
                }
            }
        }
        return s;
    }
};

//                                                     提莫攻击
 class Solution 
{
public:
    int findPoisonedDuration(vector<int>&t, int d)
    {
        int count = 0, x = 0;
        for (int i = 0; i < t.size(); i++)
        {
            if (i < t.size() - 1)
                x = t[i + 1] - t[i];
            else
                x = d;
            if (x >= d)
                count += d;
            else
                count += x;
        }
        return count;
    }
};


 //                                                     Z字形变换
 class Solution
 {
 public:
     string convert(string s, int numRows)
     {
         if (numRows == 1)
             return s;
         string ret;
         int d = 2 * numRows - 2, n = s.size();
         //处理第一行
         for (int i = 0; i < n; i += d)
             ret += s[i];

         //处理中间行
         for (int k = 1; k < numRows - 1; k++)
         {
             for (int i = k, j = d - k; i < n || j < n; i += d, j += d)
             {
                 if (i < n)
                     ret += s[i];
                 if (j < n)
                     ret += s[j];
             }
         }
         //处理最后一行
         for (int i = numRows - 1; i < n; i += d)
             ret += s[i];

         return ret;
     }
 };


 //                                                         外观数列
 class Solution
 {
 public:
     string countAndSay(int n)
     {
         string ret;
         ret = '1';
         for (int i = 1; i < n; i++)
         {
             string s;
             int size = ret.size();
             //每次解释不超过ret
             for (int left = 0, right = 0; right < size;)
             {
                 while (right < size && ret[left] == ret[right])
                     right++;
                 s += to_string(right - left) + ret[left];
                 left = right;
             }
             ret = s;
         }
         return ret;
     }
 };


 //                                                             数青蛙
 class Solution {
 public:
     int minNumberOfFrogs(string c)
     {
         unordered_map<int, int> hash;
         for (int i = 0; i < c.size(); i++)
         {
             if (c[i] == 'c')
             {
                 if (hash['k'])
                 {
                     hash['k']--;
                     hash[c[i]]++;
                 }
                 else
                     hash[c[i]]++;
             }

             if (c[i] == 'r')
             {
                 if (hash['c'])
                 {
                     hash['c']--;
                     hash[c[i]]++;
                 }
                 else
                     return -1;
             }

             if (c[i] == 'o')
             {
                 if (hash['r'])
                 {
                     hash['r']--;
                     hash[c[i]]++;
                 }
                 else
                     return -1;
             }
             if (c[i] == 'a')
             {
                 if (hash['o'])
                 {
                     hash['o']--;
                     hash[c[i]]++;
                 }
                 else
                     return -1;
             }

             if (c[i] == 'k')
             {
                 if (hash['a'])
                 {
                     hash['a']--;
                     hash[c[i]]++;
                 }
                 else
                     return -1;
             }

         }
         if (hash['c'] || hash['r'] || hash['o'] || hash['a'])
             return -1;
         return hash['k'];
     }
 };